Аннотация результатов, полученных в 2017 году
1. Протасов В.Ю. (Protasov Vladimir Yu.) Comprehensive Lyapunov functions for linear dynamical systems. Подана в журнал Automatica. Для линейных динамических переключающихся систем, была проанализирована ассимптотическая скорость роста траекторий, зависящих от начальной точки. Были рассмотрены как системы с непрерывным, так и с дискретным временем. Было доказано существование функции Ляпунова для конечномерного пространства, чьё сужение на любое инвариантное подпространсво рассматриваемой системы обеспечивает более точную оценку для скорости роста траекторй на подпространствах. Введена концепция спектральной факторизации и показано что каждая система имеет конечное число различных экспонент роста, не превышающее размерности фазового пространства. Также были исследованы свойства ляпуновской нормы и рассмотрены различные методы для ее построения. 2. Воронцова Е.А., Гасников А.В., Горбунов Э.А. (Vorontsova E.A., Gasnikov A.V., Gorbunov E.A.) Ускоренные спуски по случайному направлению с неевклидовой прокс-структурой. Подана в журнал Автоматика и Телемеханика. Для предложенного ускоренного спуска по направлению доказана оценка скорости сходимости. Приведен контрпример, показывающий сложность обобщения метода на задачи условной оптимизации. 3. Баяндина А. (Bayandina A.) Adaptive Mirror Descent for Constrained Optimization. Proceedings of Conference: Constructive Nonsmooth Analysis and Related Topics, St.Petersbourg (2017 г.) Доказано, что для решения задач выпуклой негладкой условной оптимизации может быть применён метод зеркального спуска с адаптивным выбором шага. Теперь размер шага зависит только от градиента в текущей точке. При этом скорость сходимости метода оптимальна в смысле нижних оценок, а константа сходимости улучшена благодаря адаптивности. Для сильно выпуклых задач также доказана оптимальная сходимость с улучшенной константой. Показано, что для выпуклых задач с ограничениями в форме максимума при использовании предложенного алгоритма решение прямой задачи сходится к решению двойственной, и скорость этой сходимости оптимальна. 4. Гасников А.В., Нестеров Ю.Е. (Gasnikov A.V., Nesterov Yu.) Универсальный метод для задач стохастической композитной минимизации. Принята к публикасции в Журнале Вычислительной Математики и Математической Физики. Доказаны оценки скорости сходимости метода подобных треугольников и его композитной, адаптивной и универсальной вариации. Показано, как универсальный вариант МПТ можно применять к задачам стохастической оптимизации. Получены оценки скорости сходимости метода в этом случае. 5. Нестеров Ю.Е. (Nesterov Yurii) Complexity bounds for primal-dual methods minimizing the model of objective function. Mathematical Programming (2017 г.) Для известного метод условных градиентов была предложена новая схема оценки скорости сходимости, позволяющая получать приближенные решения прямо-двойственных задач с композитной целевой функцией. Дополнительные свойства негладкой части целевой функции могут существенно ускорить скорость сходимости процесса. Был также предложен новый вариант этого метода, который имеет интерпретацию метода доверительных областей. Для этого варианта было также доказано гарантированное уменьшение полной вариации линейной модели на допустимом множестве. Наш подход также работает для квадратичных моделей. Это позволило получить первые результаты о глобальной эффективности метода доверительных областей второго порядка. 6. Двуреченский П., Гасников А., Камзолов Д. (Dvurechensky P., Gasnikov A., Kamzolov D.) Universal Intermediate Triangle Method. Подана в журнал Optimization Methods and Software. Для универсального промежуточного градиентного метода с неточным оракулом и неточным прокс-отображением и его версии для задач с сильно выпуклой целевой функцией доказаны оценки скорости сходимости. Полученные скорости сходимости являются оптимальными с точки зрения информационной теории сложности задач оптимизации. Показано, что метод позволяет на каждом шаге автоматически подбирать уровень неточности оракула и неточности прокс-отображения для того, чтобы метод в целом вычислил решение с любой наперед заданной точностью по функции. 7. Нестеров Ю.Е., Протасов В.Ю. (Nesterov Yu, Ptotasov Vladimir Yu.) Computing closest stable non-negative matrix. Подана в журнал SIMAX. Была исследована задача стабилизации для линейных динамических систем с дикретным временем, задаваемых неотрицательными матрицами. Оказалось что для построения ближайшей устойчивой матрицы в бесконечной норме существуют эффективные полиномиальные алгоритмы. Тот же факт верен и для нахождения расстояния до границы множества устойчивых матриц, если мерять расстояние в бесконечной норме. Был также рассмотрен случай полиедральных норм и столбцовых множеств неопределенности. Для такой ситуации был предложен эффективный алгоритм симплексного типа. Для рассмотренных ситуаций было получено точное описание множества устойчивости вокруг заданной матрицы. Этот результат является обобщением теоремы Харитонова об устойчивых полиномах на матричный случай. 8. Грапилия Д., Нестеров Ю.Е. (Grapiglia G., Nesterov Yu.) Accelerated regularized Newton methods for minimizing composite functions. Подана в журнал SIAM Journal on Optimization. Были изучены различные схемы ускоренного метода Ньютона с кубической регуляризацией, предназначенные для миниизации целевой функции представленной в виде суммы двух функций. Одна из них выпуклая и дважды дифференцируемая с матрицей вторых производных, удовлетворяющей условию Гельдера. А другая составляющая - это простая выпуклая функция, которая может и не являться гладкой или даже непрерывной. В случае когда параметр Гельдера известен, были разработаны методы оптимизации, существенно ускоряющие метод Ньютона. Они основаны на запоминании линейной модели целевой функции, накапливаемой за время работы алгоритма. В том же случае когда параметр Гельдера неизвестен (а это как правило так), были разработаны универсальные методы, автоматически настраивающиеся на наилучшее значение параметра. Их скорость сходимости не такая высокая как у методов с полной информацией. Тем не менее, они существенно быстрее одношаговых методов Ньютона, имеющих полную информацию о степени гладкости целевой функции. 9. Гуминов С., Гасников А., Аникин А., Горнов А. (Guminov С., Gasnikov А., Anikin А., Gornov А.) A universal modification of the linear coupling method. Принята к публикации в журнале Optimization Methods and Software Для универсального быстрого градиентного метода с вспомогательной одномерной оптимизацией проведены численные эксперименты, которые показали, что предложенный метод для негладких задач работает заметно быстрее универсального градиентного метода. Насколько нам известно, это первый универсальный метод с вспомогательной одномерной минимизацией. Были получены оценки скорости сходимости предложенного метода. Оценки оптимальны для рассматриваемого класса задач с точностью до мультипликативных констант. 10. Баяндина А. (Bayandina A.) Adaptive Stochastic Mirror Descent for Constrained Optimization. Proceedings of Conference: Constructive Nonsmooth Analysis and Related Topics. St.Petersbiug (2017 г.) Доказано, что для решения задач выпуклой негладкой условной стохастической оптимизации может быть применён метод зеркального спуска с адаптивным выбором шага. Теперь размер шага зависит только от градиента в текущей точке. При этом скорость сходимости метода в среднем оптимальна в смысле нижних оценок, а константа сходимости улучшена благодаря адаптивности. 11. Тюрин А.И., Гасников А.В. (Turin A.I., Gasnikov A.V.) Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим (δ,L)-модель функции в запрошенной точке. Подана в Журнал Вычислительной Математики и Математической Физики. Показано, что многие известные ранее конструкции методов (композитные методы, методы уровней, метод условных градиентов, проксимальные методы) являются частными случаями предложенных методов на основе (δ, L)-модели функции. 12. Нестеров Ю.Е., Шихман В. (Nesterov Yu., Shikhman V.) Dual subgradient method with averaging for optimal resource allocation. Принята к публикации в журнале EJOR. Был предложен двойственный субградиентный метод, который может решать задачи выпуклой оптимизации с линейными ограничениями. Новой чертой этого метода является возможность построения приближения к решению прямой задачи по траектории двойственного процесса. Для этого вычисляется среднее значение прямых переменных, вознимающих при вычислении значения двойственной функции. В качестве интересного приложения, метод применяется для вычисления оптимального размещения ресурсов в системе с многими независимыми агентами, имеющими собственные целевые функции. Предложенный алгоритм может быть реализован в реальных экономических системах для быстрого достижения рыночного равновесия.

Аннотация результатов, полученных в 2018 году
За 2018 в открытой печати появились следующие статьи, отражающие основные резудьтаты полученные в ходе выполнения проекта. 1. Гасников А.В., Нестеров Ю.Е. (Gasnikov A.V., Nesterov Yu.) Универсальный метод для задач стохастической композитной минимизации. Computational Mathematics and Mathematical Physics, 2018, 58(1), 48–64. (2018). В статье доказаны оценки скорости сходимости метода подобных треугольников (МПТ) и его композитной, адаптивной и универсальной вариации. Показано, как универсальный вариант МПТ можно применять к задачам стохастической оптимизации. Получены оценки скорости сходимости метода в этом случае. 2. Гуминов С., Гасников А., Аникин А., Горнов А. (Guminov С., Gasnikov А., Anikin А., Gornov А.) A universal modification of the linear coupling method. Optimization Methods and Software. Published online: Sept 2018, DOI 10.1080/10556788.2018.1517158 Для универсального быстрого градиентного метода со вспомогательной одномерной оптимизацией проведены численные эксперименты, которые показали, что предложенный метод для негладких задач работает заметно быстрее универсального градиентного метода. Насколько нам известно, это первый универсальный метод со вспомогательной одномерной минимизацией. Были получены оценки скорости сходимости предложенного метода. Оценки оптимальны для рассматриваемого класса задач с точностью до мультипликативных констант. 3. Нестеров Ю.Е., Шихман В. (Nesterov Yu., Shikhman V.) Dual subgradient method with averaging for optimal resource allocation. European Journal of Operational Research, 270, 907-916 (2018). Был предложен двойственный субградиентный метод, который может решать задачи выпуклой оптимизации с линейными ограничениями. Новой чертой этого метода является возможность построения приближения к решению прямой задачи по траектории двойственного процесса. Для этого вычисляется среднее значение прямых переменных, вознимающих при вычислении значения двойственной функции. В качестве интересного приложения, метод применяется для вычисления оптимального размещения ресурсов в системе со многими независимыми агентами, имеющими собственные целевые функции. Предложенный алгоритм может быть реализован в реальных экономических системах для быстрого достижения рыночного равновесия. 4. Нестеров Ю.Е. (Nesterov Yurii) Complexity bounds for primal-dual methods minimizing the model of objective function. Mathematical Programming, 171(1–2), 311–330 (2018) Для известного метод условных градиентов была предложена новая схема оценки скорости сходимости, позволяющая получать приближенные решения прямо-двойственных задач с композитной целевой функцией. Дополнительные свойства негладкой части целевой функции могут существенно ускорить скорость сходимости процесса. Был также предложен новый вариант этого метода, который имеет интерпретацию метода доверительных областей. Для этого варианта было также доказано гарантированное уменьшение полной вариации линейной модели на допустимом множестве. Наш подход также работает для квадратичных моделей. Это позволило получить первые результаты о глобальной эффективности метода доверительных областей второго порядка. 5. Гасников А.В., Гасникова Е.В., Нестеров Ю.Е. (A.V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov.) Dual Methods for finding Equilibriums in Mixed Models of Flow Distribution in Large Transportation Networks. Computational Mathematics and Mathematical Physics, 58(9), 1395-1403 (2018). В этой статье рассматриваются задачи нахождения равновесного распределения транспортных потоков в смешанных сетях, где часть дуг характеризуются с помощью явной функции задержок, а другая часть имеет ограниченные пропускные способности с заданным минимальным временем проезда в случае отсутствия пробок. Такие модели возникают, в частности, в случае грузовых перевозок. Специальным классом смешанных моделей является семейство комбинированных моделей Бекмана и модели стабильной динамики. Поиск равновесия в этих моделях сводится к решению специальной задачи выпуклой оптимизации. В этой статье предложен метод двойственных усреднений для решения двойсттвенной задачи. Рассматриваются два различных метода восстановления прямого решения. Показывается что предложенные алгоритмы хорошо распараллеливаются. Полученные оценки скорости сходимости соответствуют нижним оценкам сложности соответствующего класса задач негладкой оптимизации. 6. Гулельми Н., Протасов В. (N.Guglielmi, V.Yu.Protasov) On the Closest Stable/Unstable Nonnegative Matrix and Related Stability Radii. SIAM Journal of Matrix Analysis and Applications, 39(4), 1642-1669 (2018). В этой статье рассматривается задача построения ближайшей устойчивой/неустойчивой неотрицательной матрицы к заданной вещественной матрице. Расстояние между матрицами измеряется в Фробениусовой норме. Эта задача анализируется с точки зрения двух критериев устойчивости: устойчивости по Шуру (когда матрица считается устойчивой если ее спектральный радиус меньше чем единица) и устойчивостью по Гурвицу (когда матрица считается устойчивой если ее спектральная абсцисса отрицательна). Показывается что ближайшая неустойчивая матрица всегда может быть найдена в явном виде. Для нахождения ближайшей устойчивой матрицы предложен алгоритм с локальной линейной скоростью сходимости. Показывается что общее количество локальных минимумов в этой задаче может быть экспоненциально большим. Также привежены оценки сложности и результаты численных экспериментов. 7. Нестеров Ю., Шихман В. (Nesterov Yu, Shikhman V.) Computation of Fisher–Gale Equilibrium by Auction. Journal of Operations Research Society China, DOI: 10.1007/s40305-018-0195-5 (2018). В этой статье с алгоритмической точки зрения рассматривается модель Фишера для нахождения рыночного равновесия в условиях конкуренции. Для этого используется соответствующая задача выпуклой оптимизации предлоденная Gale and Eisenberg (Ann Math Stat 30(1):165–168, 1959). Известно что эта модель приводит к равновесию по Фишеру только при некоторых структурных предположениях о функции полезности потребителей (например, однородности степени единица, гомотетичности, и т.д.). Наша цель состояла в проверке применимости Выпуклой Оптимизации при отсутствии этих стандартных предположений. Мы предполагаем только вогнутость функции полезности. Для этого случае удается сформулировать новую концепцию равновесия Фишера-Гейла, основанную только на индивидуальных ценах на полезность. Эти цены позволяют сравнивать полезности различных вариантов потребления. В свою очередь, становится возможным применить для этой ситуации метод оптимизации субградиентного типа. Для децентрализации цен мы вводим вспомоготельный аукцион на котором потребители устанавливают и пресчитывают свои цены, а производители продают продукты по максимальной предложенной цене. Адаптация цен происходит пропорционально избытку спроса над предложением. Показано что исторически средние объемы производств сходятся к равновесным величинам. Наш метод обладает гарантированной скоростью сходимости, характерной для алгоритмов негладкой оптимизации. 8. Чиконе А.,Гулильми, Протасов В. (A.Cicone, N.Guglielmi, V.Yu.Protasov) Linear dynamical switching systems on graphs. Nonlinear Analysis: Hybrid Systems, 29, !65-186 (2018). В статье рассматриваются линейные динамические системы со структурой мультиграфа. В этом графе вершины ассоциируются с линейными пространствами, а ребра соответствуют линейным отображениям между этими простраствами. Мы анализируем ассимтотический рост траекторий (ассоциированных с путями в мультиграфе), стабильность и стабилизируемость задач. Эти рассмотрения обобщают классисческие линейные переключающиеся системы вместе с их недавним расширением на Марковские системы на системы генерируемые регулярными языками. Показывантся что любая система может быть разложена на несколько неприводимых систем соответсвующих сильно связанному мультиграфу. Для таких систем мы доказываем существование инвариантой (Барабановской) мультинормы и предлагаем метод ее построения. Наш метод работаает для обширного класса систем и находит их совместный спектральный радиус (Ляпуновская экспонента). Мы приводим также результаты численных экспериментов и рассматриваем приложения, полезные для изучения фракталов, аттракторов и многошаговых методов для Обыкновенных Дифференциальных Уравнений.

Аннотация результатов, полученных в 2019 году
Предложен универсальный прямо-двойственный ускоренный градиентный метод со вспомогательной одномерной оптимизацией. Особенностью метода является возможность работы в отсутствии знаний информации об оптимизируемой функции. Функция может быть невыпуклой, может быть выпуклой, но негладкой. Методу ничего этого не надо знать, равно как и соответствующих констант гладкости. Метод сам настраивается адаптивно и на гладкость и на выпуклость. Важной особенностью метода является его прямо-двойственность на классе выпуклых задач. Получены оценки скорости сходимости метода во всех режимах. Причем оценки соответствуют нижним оценкам для рассматриваемых классов задач. Проведены численные эксперименты для сравнения предложенного метода с методом сопряженных градиентов и квазиньютоновскими методами, показавшие преимущество нового метода. Разработанные в проекте варианты ускоренных градиентных методов применены к существенно невыпуклым задачам минимизации функции энергии, описывающей состояние макромолекул в задачах белкового фолдинга и докинга. Отличительной особенностью задачи является ее большая размерность и квадратичная по размерности стоимость вычисления градиента и значения целевой функции. Экспериментально показано, что специальные адаптивные варианты разрабатываемых в проекте ускоренных методов хорошо решают данные задачи и конкурируют с лучшими известными сейчас методами для этих задач. Полученные результаты открывают возможности применения разрабатываемых в проекте методов оптимизации к задачам разработки лекарств и дизайна материалов. Предложен общий подход построения ускоренных рандомизированных методов для выпуклой оптимизации, включая безградиентные методы, спуски по направлению, покомпонентные методы. Предложенные методы работают в предположении неточного оракула, то есть при наличии зашумленной информации о производных и значениях целевой функции. Для безградиентных методов это является важным аспектом в виду некорректности численного дифференцирования. Получены оценки скорости сходимости методов в предположении выпуклости, а также при наличии дополнительного предположения о сильной выпуклости. Подход позволил получить как известные методы, так и новые, например, ускоренный блочно-покомпонентный метод с неевклидовой проксимальной структурой. Описан общий (ускоренный) способ работы с задачами структурной (композитной, max-задачами и т.п.) оптимизации путем введения концепции неточной модели функции, обобщающей концепцию (\delta, L)-оракула (Деволдер-Глинер-Нестеров, 2013). Особенностью подхода является возможность работы также в концепции относительной гладкости в неускоренном случае. Предложено обобщение ускоренного градиентного метода для задач при наличии неточной модели целевой функции, получена оценка его скорости сходимости, а также оценка на скорость накопления неточности и ошибки проектирования на допустимое множество. В качестве частного случая получены метод условного градиента, ускоренный метод с неточным оракулом. Были рассмотрены методы с переменной метрикой из класса квазиньютоновских методов. Основной целью являлось получение оценок скорости локальной и глобальной сходимости методов. Для методов из этого класса на текущий момент известно, что глобальная скорость сходимости не лучше, чем у градиентного метода, а локальная скорость сходимости является сверхлинейной. Однако, показатель скорости сходимости неизвестен. Кроме того, исследовались возможности ускорения градиентных методов в невыпуклом случае за счет введения переменной метрики. Разработан жадный алгоритм для минимизации/максимизации спектрального радиуса на специальных семействах неотрицательных матриц. Алгоритм демонстрирует свою исключительную эффективность даже в размерностях несколько тысяч. Указаны приложения данного метода к теории графов, теории линейных динамических cистем с переключениями и к ряду задач математической экологии (матричные модели популяционной динамики). При этом для борьбы с зацикливанием предложено понятие обобщенного перроновского вектора неотрицательной матрицы. В отличие от обычного перроновского вектора, который может быть не единственным, обобщенный вектор всегда единственный с точностью до нормировки. Для него указана явная формула и предложен эффективный алгоритм его вычисления. Идея жадного алгоритма оптимизации спектрального радиуса лежит в основе нового метода поиска ближайшей устойчивой/неустойчивой матрицы к данной неотрицательной матрице. Показано, что в норме $L_{\infty}$ эта задача всегда имеет выпуклое множество точек абсолютного минимума. Для поиска ближайшей матрицы разработан эффективный алгоритм. Напомним, что в норме Фробениуса та же задача может иметь экспоненциальное по размерности число изолированных точек локального минимума, и эффективные алгоритмы минимизации неизвестны. Предложенный метод поиска ближайшей устойчивой матрицы применен к известной задаче о поиске максимально ацикличного подграфа заданного графа (MAS – maximal acyclic subgraph). Для ослабленной версии этой задачи, когда минимизируется максимальное число обрезанных ребер, взятое по всем вершинам, данный метод эффективно ищет оптимальный подграф. Для задачи MAS данный метод дает приближенное решение с фактором порядка 0.6. Кроме запланированных на 2019 год работ и результатов проведены также следующие работы и получены следующие результаты Предложен ускоренный безградиентный метод с неевклидовой проксимальной структурой и неточными значениями целевой функции. Отличительной особенностью метода является сочетание градиентного шага в 2-норме и шага метода зеркального спуска в 1-норме. Доказана специальная лемма о концентрации случайной величины на шарах в разной норме. Доказано, что рассогласование нормы для шагов позволяет выиграть в теоретической зависимости оценки скорости сходимости порядка корня из размерности в случае, если решение задачи является разреженным. Таким образом теоретическая оценка для метода является наилучшей из известных ускоренных безградиентных методов. Проведены численные эксперименты, показавшие эффективность метода на практике. Предложены имплементируемые тензорные методы, использующие производные произвольного порядка. Основное предполложение - производная порядка p является Липшицевой. Предложены нижние оценки для задач такого класса, а также тензорные и ускоренные тензорные методы, имеющие почти оптимальные оценки. Для методов третьего порядка с помощью подхода относительной гладкости показано, что каждая итерация метода третьего порядка требует вычислительных затрат примерно столько же, сколько методы второго порядка. При этом по теоретическим оценкам метод третьего порядка сходится быстрее, чем метод второго порядка. Предложены адаптивные тензорные методы для выпуклой минимизации функций, имеющих Липшицеву производную произвольного порядка. Доказана оценка скорости сходимости, которая с точностью до логарифмического фактора является оптимальной в данном классе. Метод обобщен на класс равномерно выпуклых функций, для которого получена оценка скорости сходимости, в том числе в определенном классе задач линейная. Предложено обобщенное число обусловленности для функций рассматриваемого класса. Проведены численные эксперименты, показавшие, что метод третьего порядка работает быстрее, чем метод второго порядка. Предложен прямо-двойственный адаптивный быстрый градиентный метод для задач с линейными ограничениями и применен для задачи вычисления расстояния Васерштейна между вероятностными мерами, имеющей широкое применение к задачам машинного обучения. Получена оценка сложности для задач оптимального транспорта, в определенных режимах являющаяся лучшей, чем оценка для используемого в литературе метода Синхорна. Кроме того, в получена улучшенная оценка сложности для метода Синхорна. Показано, что в режиме невысокой точности, который характерен для приложений в машинном обучении из-за наличия шума в данных, предложенный ускоренный градиентный метод теоретически работает быстрее, чем метод Синхорна. Теоретический результат также подтвержден численными экспериментами.